/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package pt.utl.ist.isr.livetrack.analysis.util;

import java.util.Arrays;
import org.apache.log4j.Logger;

/**
 *
 * @author David Miguel Antunes <davidmiguel [ at ] antunes.net>
 */
public class UnionFind {

    private static final Logger logger = Logger.getLogger(UnionFind.class.getName());
    private int[] id;
    private int[] size;
    private int nComponents;

    public UnionFind(int n) {
        id = new int[n];
        size = new int[n];
        nComponents = n;
        reset();
    }

    public void reset() {
        Arrays.fill(size, 1);
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    public int find(int i) {
        while (id[i] != i) {
            i = id[i];
        }
        return i;
    }

    public int getnComponents() {
        return nComponents;
    }

    public void unite(int i, int j) {
        int iComp = find(i);
        int jComp = find(j);
        if (iComp == jComp) {
            return;
        }
        if (size[iComp] < size[jComp]) {
            id[iComp] = jComp;
            size[jComp] = size[jComp] + size[iComp];
        } else {
            id[jComp] = iComp;
            size[iComp] = size[iComp] + size[jComp];
        }
        nComponents--;
    }

    public int[] getGroupNames() {
        int[] names = new int[nComponents];
        int idIdx = 0;
        for (int i = 0; i < nComponents; i++) {
            while (id[idIdx] != idIdx) {
                idIdx++;
            }
            names[i] = idIdx;
        }
        return names;
    }
}
